//
// Created by fh on 2021/6/3.
//

#include "LinkBiTree.h"

static time = 0;

/* 二叉树的前序遍历递归算法 */
void BiTreePreOrderTraverse(BiTreeNode *rootNode) {
    time++;
    if (rootNode == NULL) {
        return;
    }
    printf("%d\n",rootNode->data); /*显示结点数据，可以更改为其他对结点操作*/
    BiTreePreOrderTraverse(rootNode->leftChild); /*再先序遍历左子树*/
    BiTreePreOrderTraverse(rootNode->rightChild); /*最后先序遍历右子树*/
}

/* 二叉树的中序遍历递归算法 */
void BiTreeInOrderTraverse(BiTreeNode *rootNode) {
    if (rootNode == NULL) {
        return;
    }
    BiTreeInOrderTraverse(rootNode->leftChild);
    printf("%d\n",rootNode->data);
    BiTreeInOrderTraverse(rootNode->rightChild);
}

/* 二叉树的后序遍历递归算法 */
void BiTreePostOrderTraverse(BiTreeNode *rootNode) {
    if (rootNode == NULL) {
        return;
    }
    BiTreePostOrderTraverse(rootNode->leftChild);
    BiTreePostOrderTraverse(rootNode->rightChild);
    printf("%d\n",rootNode->data);
}

/* 按前序遍历输入二叉树中结点的值 */
void BiTreePreCreateBiTree(BiTreeNode **t) {
    int input;
//    input = random() % 100 + 1;
    scanf("%d",&input);
    if (input == 0) {
        *t = NULL;
    } else {
        *t = (BiTreeNode *) malloc(sizeof(BiTreeNode));
        if (*t == NULL) {
            return;
        }
        (*t)->data = input;
        BiTreePreCreateBiTree(&(*t)->leftChild);
        BiTreePreCreateBiTree(&(*t)->rightChild);
    }
}

/* 生成一棵树，返回根节点 */
BiTreeNode * BiTreeCreateBiTree() {
    BiTreeNode *root = (BiTreeNode *) malloc(sizeof(BiTreeNode));
    if (root == NULL) {
        return NULL;
    }
    BiTreePreCreateBiTree(&root);
    return root;
}

/* 自定义打印前序遍历 */
void BiTreeCustomDisplay(BiTreeNode *rootNode) {
    if (rootNode == NULL) {
        return;
    }
    printf("结点%p的值是%d,左孩子是:%d,右孩子是:%d\n",rootNode->data,rootNode->leftChild->data,rootNode->rightChild->data);
    BiTreeCustomDisplay(rootNode->leftChild);
    BiTreeCustomDisplay(rootNode->rightChild);
}

/* 叶子结点有序插入:左子树小，右子树大 */
Status BiTreeOrderlyInsertNode(BiTreeNode **root,int e) {
    if (root == NULL) {
        return ERROR; /* 外部传进来的指针的地址是空的 */
    }
    BiTreeNode *p = *root;
    // 第一种方法
    /*
    if (p == NULL) {
        p = (BiTreeNode *) malloc(sizeof(BiTreeNode));
        p->data = e;
        p->leftChild = NULL;
        p->rightChild = NULL;
        *root = p;  // 这行代码可以避免开辟了内存然后丢失了对这块内存的引用问题，即内存泄漏，此外p只是函数里的临时变量，开辟的内存需要给外部实参赋值，简单地通过p赋值是不行的
        return OK;
    }
    //*/
    ///*
    // 第二种方法
    if (*root == NULL) {
        *root = (BiTreeNode *) malloc(sizeof(BiTreeNode));
        (*root)->data = e;
        (*root)->leftChild = NULL;
        (*root)->rightChild = NULL;
        return OK;
    }
    //*/

    /* 这里面如果直接修改*root的话那么最后结果*root会指向插入的结点的父结点，所以p指针起到一个临时索引的作用，
     * 如果循环内部直接使用*root来操纵的话，在跳出循环之后需要让*root重新指向根节点，可以在一开始用p保存一下根节点在最后返给他 */
    while (p != NULL) {
        if (e == p->data) {
            // 相等不用插入
            printf("已经存在一样的值了\n");
            return ERROR;
        } else if (e < p->data) {
            // 比较左子树
            if (p->leftChild == NULL) {
                BiTreeNode *node = (BiTreeNode *) malloc(sizeof(BiTreeNode));
                node->data = e;
                node->leftChild = NULL;
                node->rightChild = NULL;
                /*
                 * 这里可以用自动变量p来操作原来实参的值是因为当p不为空的时候实际上p->leftChild = node它操作的是跟实参的结点一样的内存地址，
                 * p是指向结构体的地址，所以能够操纵修改结构里的属性值
                 * */
                p->leftChild = node;
                break;
            } else {
                // 循环比较
                p = p->leftChild;
            }
        } else {
            if (p->rightChild == NULL) {
                BiTreeNode *node = (BiTreeNode *) malloc(sizeof(BiTreeNode));
                node->data = e;
                node->leftChild = NULL;
                node->rightChild = NULL;
                /*
                 * 这里可以用自动变量p来操作原来实参的值是因为当p不为空的时候实际上p->leftChild = node它操作的是内存地址，
                 * p是指向结构体的地址，所以能够操纵修改结构里的属性值
                 * */
                p->rightChild = node;
                break;
            } else {
                // 循环比较
                p = p->rightChild;
            }
        }
    }
    return OK;
}

/* 叶子结点删除:左子树小，右子树大,删除值为e的结点 */
Status BiTreeOrderlyDeleteNode(BiTreeNode *root,int e) {
    BiTreeNode *p = root;
    BiTreeNode *father = NULL;
    int temp = 0;
    while (p != NULL) {
        if (e < p->data) {
            father = p;
            p = p->leftChild;
            temp = 1;
        } else if (e > p->data) {
            father = p;
            p = p->rightChild;
            temp = 2;
        } else {
            break;
        }
    }
    if (p == NULL) {
        printf("没有找到要删除的点\n");
        return ERROR;
    }
    printf("第一步,找值,找到的值为：%d\n",p->data);
    if (father == NULL) {
        printf("该结点是根节点,他没有父结点\n");
    } else {
        printf("他的父亲的值为：%d\n",father->data);
    }

    // 是叶子结点，直接删掉
    if (p->leftChild == NULL && p->rightChild == NULL) {
        if (temp == 1) {
            // 是左结点
            father->leftChild = NULL;
            free(p);
            p = NULL;
        } else if (temp == 2) {
            // 是右结点
            father->rightChild = NULL;
            free(p);
            p = NULL;
        }
    } else if (p->leftChild == NULL && p->rightChild != NULL) {
        // 只有右子树
//        // 不能这么写，因为你不知道你的孩子是不是有左右孩子，如果有，你是不能删掉那个结点的
//        p->data = p->rightChild->data;
//        free(p->rightChild);
//        p->rightChild = NULL;
        // 正确操作是将要删除的父节点连接到子节点
        if (temp == 1) {
           father->leftChild = p->rightChild;
        } else if (temp == 2) {
            father->rightChild = p->rightChild;
        }

    } else if (p->leftChild != NULL && p->rightChild == NULL) {
        // 只有左子树
//        // 不能这么写，因为你不知道你的孩子是不是有左右孩子，如果有，你是不能删掉那个结点的
//        p->data = p->leftChild->data;
//        free(p->leftChild);
//        p->leftChild = NULL;
        // 正确操作是将要删除的父节点连接到子节点
        if (temp == 1) {
            father->leftChild = p->leftChild;
        } else if (temp == 2) {
            father->rightChild = p->leftChild;
        }
    } else {
        // 删除的结点有两个孩子的情况，它的双亲不能连接到它的两个孩子:
        // 删除策略是不删除这个结点，而是删除它的左子树中值最大的那个结点，并用这个值代替原先应被删除的那个结点的值
        BiTreeNode *q = p->leftChild;
        BiTreeNode *qf = p;
        while (q != NULL) {
            if (q->rightChild == NULL) {
                break;
            } else {
                qf = q;
                q = q->rightChild;
            }
        }
        // 删掉q
        if (q != NULL) {
            // 用这个值代替原先应被删除的那个结点的值
            p->data = q->data;
            // 删掉它的左子树中值最大的那个结点
            // 此时q可能有或者没有左孩子，但是一定没有右孩子
            if (qf == p) {
                // 此时要修改的是p的左孩子,这种情况其实要删除的结点刚好是p的左子树的第一个结点
                // 这种情况是要删除的结点的左子树里没有右子树
                qf->leftChild = q->leftChild;
            } else {
                qf->rightChild = q->leftChild;
            }
            free(q);
            q = NULL;
        }
    }
    return OK;
}

/* 叶子结点查找:左子树小，右子树大,查找值为e的结点 */
Status BiTreeOrderlyModifyNode(BiTreeNode *root,int e,BiTreeNode **resultNode) {
    BiTreeNode *p = root;
    while (p != NULL) {
        if (e < p->data) {
            p = p->leftChild;
        } else if (e > p->data) {
            p = p->rightChild;
        } else {
            printf("找到了:%p - %d\n",p,p->data);
            break;
        }
    }
    if (p == NULL) {
        printf("没有找到该值\n");
        return ERROR;
    }
    *resultNode = p;
    return OK;
}


/* 测试demo */
void BiTreeTestDemo() {

    {
        BiTreeNode *root = NULL;

        int a[] = {60,50,10,55,5,40,11,3,1,12,41,70,78,72};
        int length = sizeof(a) / sizeof(int);
        printf("数组长度：%d\n", length);
        for (int i = 0; i < length; ++i) {
            int value = a[i];
            Status result = BiTreeOrderlyInsertNode(&root,value);
            printf("插入结果：%d\n",result);
        }
        printf("前序遍历: \n");
        BiTreePreOrderTraverse(root);

        printf("time = %d\n",time);
        time = 0;

        //*
        Status result = BiTreeOrderlyDeleteNode(root,60);
        printf("删除结果：%d\n",result);
        printf("删除第一次前序遍历: \n");
        BiTreePreOrderTraverse(root);
        printf("time = %d\n",time);

        BiTreeNode *findNode = NULL;
        BiTreeOrderlyModifyNode(root,10,&findNode);
        if (findNode != NULL) {
            printf("%d\n", findNode->data);
        }
        findNode = NULL;
        BiTreeOrderlyModifyNode(root,110,&result);
        if (findNode != NULL) {
            printf("%d\n", findNode->data);
        }
        //*/

    }
    return;
    {
        BiTreeNode *root = NULL;
        Status result = BiTreeOrderlyInsertNode(&root,10);
        printf("插入结果：%d\n",result);
        result = BiTreeOrderlyInsertNode(&root,2);
        printf("插入结果：%d\n",result);
        result = BiTreeOrderlyInsertNode(&root,12);
        printf("插入结果：%d\n",result);
        result = BiTreeOrderlyInsertNode(&root,1);
        printf("插入结果：%d\n",result);
        result = BiTreeOrderlyInsertNode(&root,16);
        printf("插入结果：%d\n",result);
        result = BiTreeOrderlyInsertNode(&root,9);
        printf("插入结果：%d\n",result);
        result = BiTreeOrderlyInsertNode(&root,11);
        printf("插入结果：%d\n",result);
        result = BiTreeOrderlyInsertNode(&root,56);
        printf("插入结果：%d\n",result);
        result = BiTreeOrderlyInsertNode(&root,16);
        printf("插入结果：%d\n",result);

        printf("前序遍历: \n");
        BiTreePreOrderTraverse(root);

        BiTreeOrderlyDeleteNode(root,13);


//        for (int i = 0; i < 6; ++i) {
//            int a = random() % 100;
//            result = BiTreeOrderlyInsertNode(&root,a);
//            printf("插入结果：%d\n",result);
//        }
//        printf("前序遍历: \n");
//        BiTreePreOrderTraverse(root);

    }
    return;
    {
        BiTreeNode *t = BiTreeCreateBiTree();
        if (t == NULL) {
            return;
        }
        printf("前序遍历：\n");
        BiTreePreOrderTraverse(t);
//    BiTreeCustomDisplay(t);
    }

}










